◀ Prev · Parts · Full · Next ▶

• In a chemical reaction network (a finite set of reactions like A+B → 2C + D operating on a finite number of molecules), the ability to ever reach a given target state from an initial state is decidable, while even approximating the probability of ever reaching a given target state (using the standard concentration-based probability for which reaction will occur next) is undecidable. More specifically, a limited Turing machine can be simulated with arbitrarily high probability of running correctly for all time, only if a random chemical reaction network is used. With a simple nondeterministic chemical reaction network (any possible reaction can happen next), the computational power is limited to primitive recursive functions.cite-ref-30[30]

• Approximate counting algorithm

• Atlantic City algorithm

• Bogosort

• Count–min sketch

• HyperLogLog

• Karger's algorithm

• Las Vegas algorithm

◀ Prev · Parts · Full · Next ▶